
//给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

//插入排序 算法的步骤 :

//插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
///每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
//重复直到所有输入数据插入完为止。
//下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

//对链表进行插入排序。typedef struct ListNode ListNode;
ListNode* insertionSortList(ListNode* head)
{
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    ListNode* sortHead = head;//排序链表的头节点
    ListNode* cur = head->next;//原链表的遍历符号
    sortHead->next = NULL;//
    ListNode* sortcur = sortHead;//定义遍历排序数组符号
    while (cur)
    {
        ListNode* next = cur->next;//存储下一个节点地址，以防找不到
        if (sortHead->val >= cur->val)
        {
            //头插
            cur->next = sortHead;
            sortHead = cur;
        }
        else
        {
            //尾插或者中间插
            ListNode* sortprev = sortHead;//定义前符号以便中间插入或者尾插
            sortcur = sortprev->next;
            while (sortcur)
            {
                if (cur->val <= sortcur->val)
                {
                    //中间插入
                    cur->next = sortprev->next;
                    sortprev->next = cur;
                    break;
                }
                else
                {
                    sortprev = sortcur;
                    sortcur = sortcur->next;
                }
            }
            //尾插
            if (sortcur == NULL)
            {
                sortprev->next = cur;
                cur->next = NULL;
            }
        }
        cur = next;
    }
    return sortHead;
}